package lib

//Link to 188
func init() {
	Probs = append(Probs, Problem{
		Num:         309,
		Discription: "带冷却期的最多k笔股票买卖最大收益",
		Level:       3,
		Labels: map[string]int{
			"动态规划":  1,
			"有限状态机": 1,
		},
	})
}

func MaxProfit5(prices []int) int {
	n := len(prices)
	if n <= 1 {
		return 0
	}

    //hold[i]表示0-i天这个范围内持有股票的最大收益（最小成本）
	hold := make([]int, n)
	sold := make([]int, n)
	cooldown := make([]int, n)
	hold[0] = -prices[0]
	sold[0] = 0
	cooldown[0] = 0

	for i := 1; i < n; i++ {
		hold[i] = max(hold[i-1], cooldown[i-1]-prices[i])
		sold[i] = max(sold[i-1],hold[i-1]+prices[i])
		cooldown[i] = max(cooldown[i-1], sold[i-1])
	}

	return max(sold[n-1], cooldown[n-1])
}